/*
 * Copyright (C) 2011-2013 Eric Lasota
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */
#ifndef __RDX_LUT_HPP__
#define __RDX_LUT_HPP__

#include "rdx_basictypes.hpp"
#include "rdx_utility.hpp"
#include <stdio.h>

namespace RDX
{
	namespace Programmability
	{
		class String;
	}

	template<class _TindexCharType, class _TactualCharType>
	class StaticLookupStringKey
	{
	private:
		const _TactualCharType *_value;
		LargeInt _len;
		HashValue _hashValue;
		bool _valid;

	public:
		inline StaticLookupStringKey(const _TactualCharType *str, LargeInt len)
		{
			Utility::IntermediateHash hv;
			_valid = true;

			for(LargeInt i=0;i<len;i++)
			{
				_TindexCharType lc = static_cast<_TindexCharType>(str[i]);
				if(static_cast<_TactualCharType>(lc) != str[i])
					_valid = false;
				hv.FeedBytes(&lc, sizeof(_TindexCharType));
			}

			_value = str;
			_len = len;
			_hashValue = hv.Flush();
		}

		inline StaticLookupStringKey(const _TactualCharType *str)
		{
			Utility::IntermediateHash hv;
			_valid = true;
			LargeInt len;
			for(len=0;str[len];len++)
			{
				_TindexCharType lc = static_cast<_TindexCharType>(str[len]);
				if(static_cast<_TactualCharType>(lc) != str[len])
					_valid = false;
				hv.FeedBytes(&lc, sizeof(_TindexCharType));
			}

			_value = str;
			_len = len;
			_hashValue = hv.Flush();
		}

		inline HashValue Hash() const
		{
			return _hashValue;
		}

		inline bool IsValid() const
		{
			return _valid;
		}

		inline LargeInt Length() const
		{
			return _len;
		}

		inline const _TactualCharType *Chars() const
		{
			return _value;
		}

		template<class _TrsActualCharType>
		inline bool operator ==(const StaticLookupStringKey<_TindexCharType, _TrsActualCharType> &rs) const
		{
			if(this->_valid == false || rs.IsValid() == false || rs.Length() != this->_len)
				return false;
			LargeInt len = _len;
			const _TactualCharType *c1 = _value;
			const _TrsActualCharType *c2 = rs.Chars();
			while(len--)
			{
				const _TindexCharType lChar = static_cast<_TindexCharType>(*c1++);
				const _TindexCharType rChar = static_cast<_TindexCharType>(*c2++);
				if(lChar != rChar)
					return false;
			}
			return true;
		}
	};

	template<class _Tvalue>
	class StaticLookupPODKey
	{
	private:
		_Tvalue _value;
		HashValue _hashValue;

	public:
		inline StaticLookupPODKey(const _Tvalue &v)
		{
			_value = v;
			_hashValue = Utility::HashBytes(&v, sizeof(_Tvalue));
		}

		inline HashValue Hash() const
		{
			return _hashValue;
		}

		inline const _Tvalue &Value() const
		{
			return _value;
		}

		inline bool operator ==(const StaticLookupPODKey<_Tvalue> &rs) const
		{
			return rs._value == this->_value;
		}
	};

	template<class _Tkey, class _TlookupType>
	class StaticLookupTable
	{
	public:
		typedef _Tkey LUTKey;
		typedef _TlookupType LUTValue;

		struct Entry
		{
			LUTKey key;
			LUTValue value;

			struct HashState
			{
				bool containsData;
				LargeInt collisionDepth;	// Max entries to search when starting here
				Entry *itemTarget;			// Where the entry is located now
				Entry *itemSource;			// Where the entry was originally located
			} hashState;
		};

	private:
		Entry *_entries;
		LargeInt _numEntries;
		bool _useAddrLookup;

		inline LargeInt HashToLocation(HashValue hv, LargeInt numEntries) const
		{
			return static_cast<LargeInt>(static_cast<UInt32>(hv) % static_cast<UInt32>(numEntries));
		}

	public:

		template<class _TlookupKey>
		inline const LUTValue *Lookup(const _TlookupKey &key) const
		{
			HashValue hv = key.Hash();

			LargeInt startingLocation = HashToLocation(hv, _numEntries);
			LargeInt location = startingLocation;
			LargeInt collisionDepth = _entries[startingLocation].hashState.collisionDepth;
			while(true)
			{
				const Entry *e = _entries + location;
				if(e->key == key)
					return &e->value;

				location++;
				if(location == _numEntries)
					location = 0;
				if(location == startingLocation)
					return NULL;
				collisionDepth--;
				if(collisionDepth == 0)
					return NULL;
			}
		}

		template<class _TlookupKey>
		inline LUTValue *Lookup(const _TlookupKey &key)
		{
			HashValue hv = key.Hash();

			LargeInt startingLocation = HashToLocation(hv, _numEntries);
			LargeInt location = startingLocation;
			LargeInt collisionDepth = _entries[startingLocation].hashState.collisionDepth;
			while(true)
			{
				Entry *e = _entries + location;
				if(e->key == key)
					return &e->value;

				location++;
				if(location == _numEntries)
					location = 0;
				if(location == startingLocation)
					return NULL;
				collisionDepth--;
				if(collisionDepth == 0)
					return NULL;
			}
		}

		inline StaticLookupTable(Entry *entries, LargeInt numEntries)
		{
			_entries = entries;
			_numEntries = numEntries;

			for(LargeInt i=0;i<numEntries;i++)
			{
				entries[i].hashState.containsData = false;
				entries[i].hashState.collisionDepth = 0;
				entries[i].hashState.itemTarget = entries + i;
				entries[i].hashState.itemSource = entries + i;
			}

			for(LargeInt i=0;i<numEntries;i++)
			{
				Entry *entry = entries[i].hashState.itemTarget;
				// Find a place to insert this
				LargeInt location = HashToLocation(entry->key.Hash(), numEntries);
				LargeInt initialLocation = location;
				LargeInt depth = 1;
				while(entries[location].hashState.containsData)
				{
					depth++;
					location++;
					if(location == numEntries)
						location = 0;
				}

				if(entries[initialLocation].hashState.collisionDepth < depth)
					entries[initialLocation].hashState.collisionDepth = depth;

				Entry *swapTarget = entries + location;
				if(swapTarget != entry)
				{
					Entry tempEntry = *entry;
					*entry = *swapTarget;
					*swapTarget = tempEntry;

					swapTarget->hashState.itemSource->hashState.itemTarget = swapTarget;
					entry->hashState.itemSource->hashState.itemTarget = entry;
				}

				swapTarget->hashState.containsData = true;
			}
		}

	};
};


#endif
